package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class p31剑指栈的压入弹出序列 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //输入两个整数序列
        //第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

        //将传入的数组转换成线性表,因为数组统计个数、判空麻烦
        List<Integer> pushedList=intArrayToList(pushed);
        List<Integer> popedList=intArrayToList(popped);

        Stack<Integer> stack=new Stack<>();

        // 实现Iterable接口的对象都可以用foreach遍历
        for(int e:popedList) {
            //挨个遍历popedList中的元素是否符合栈弹出的正确顺序
            if(!stack.isEmpty() && stack.peek()==e) {
                //测试栈中不为空，且测试栈顶元素与元素e相同
                //则当前遍历的元素e符合栈弹出的正确顺序,弹出测试栈顶元素
                //遍历下一个popedList元素
                stack.pop();
                continue;//终止当前循环，并继续执行下一次循环
            }

            //测试栈中为空，且测试栈顶元素与元素e不相同
            //要将pushedList中的元素依次压入测试栈，直至与元素e相同
            //或者pushedList中的元素全部进栈
            while(true) {
                if(pushedList.isEmpty()) {
                    //pushedList中的元素全部进栈也没有与元素e相同，即顺序错误
                    return false;
                }

                //pushedList不为空，将pushedList的元素拿出与e比较
                int f=pushedList.remove(0);
                if(f==e) {
                    //如果f==e，就可以遍历popedList中的下一个元素
                    break;//break跳出当前循环，并执行当前循环之后的语句
                          //结束while循环，进入popedList中的下一个元素
                }
                stack.push(f);
            }
        }

        return stack.isEmpty();//????

    }

    //将传入的数组转换成线性表存储
    private List<Integer> intArrayToList(int[] array) {
        //创建一个线性表
        List<Integer> list=new ArrayList<>();//List是个接口，需要具体类实例化
        for(int e:array) {
            list.add(e);//尾插
        }
        return list;
    }
}
